package leetcode.jianzhioffer;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-11-18 22:28
 **/
public class JianZhiOffer51 {

    /*public int reversePairs(int[] nums) {
        int len = nums.length;
        int count = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (nums[i] > nums[j]) {
                    count++;
                }
            }
        }
        return count;
    }*/

    int count = 0;

    public int reversePairs(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return 0;
        }
        split(nums, 0, len - 1);
        return count;
    }

    void split(int[] nums, int start, int end) {
        if (start == end) {
            return;
        }
        int mid = (start + end) >> 1;
        split(nums, start, mid);
        split(nums, mid + 1, end);
        merge(nums, start, mid, end);
    }

    void merge(int[]nums, int start, int mid, int end) {
        int[] tmp = new int[end - start + 1];
        int i = start;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= end) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                count += (mid + 1 - i);
                tmp[k++] = nums[j++];
            }
        }
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= end) {
            tmp[k++] = nums[j++];
        }

        for (int i1 = 0; i1 < tmp.length; i1++) {
            nums[start + i1] = tmp[i1];
        }
    }
    public static void main(String[] args) {
        JianZhiOffer51 offer = new JianZhiOffer51();
        System.out.println(offer.reversePairs(new int[]{7, 6, 5, 4}));
    }
}
